home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / cgazv5n5.arc / LZW1.C < prev    next >
C/C++ Source or Header  |  1991-09-23  |  9KB  |  268 lines
  1. /*--- LZW1.C ----------------------------- Listing 2 ------
  2. * Contents:  This is the compression portion of the
  3. *            LZW data compression program.  It
  4. *            contains the following routines:
  5. *               compression_routine
  6. *               write_out_code
  7. *               wk_is_in_table
  8. *               put_wk_in_table
  9. *               build_string
  10. *               create_string
  11. *               append_char
  12. *               initialize
  13. *
  14. * Author:   Dwayne Phillips
  15. * Compiler: Microsoft C 6.0a, BC++ 2.0
  16. *           Note: Must link with at least an 8K stack
  17. * Switches: DEBUG - if defined, debugging data is shown
  18. *           STATS - if defined, statistics are given
  19. * Date:     February 1991
  20. * May be used freely if authorship is acknowledged
  21. *--------------------------------------------------------*/
  22. #include "lzw.h"
  23.  
  24. /*--------------------------------------------------------
  25.  * This is the main routine for the compression process.
  26.  *-------------------------------------------------------*/
  27. void compression_routine( table_item *string_table,
  28.                           FILE *infile, FILE *outfile )
  29. {
  30.     unsigned char in_buffer[IB_LENGTH_C], w[100];
  31.     unsigned  bytes_read;
  32.     unsigned  in_counter, out_counter;
  33.     code_type out_buffer[OB_LENGTH_C], w_code;
  34.     unsigned  table_max;
  35.  
  36.     /* start up */
  37.     table_max  = initialize ( string_table );
  38.     bytes_read = my_read ( infile, in_buffer,
  39.                           sizeof(unsigned char), IB_LENGTH_C );
  40.     SHOW( printf( "\nIn: "); )
  41.     SHOW( printf ( isprint ( in_buffer[0]) ? "'%c'" : "%3dd",
  42.                    in_buffer[0]); )
  43.     create_string ( w, in_buffer[0] );
  44.     w_code = in_buffer[0];
  45.     SHOW( { unsigned char *s; printf ( " w: '" ); )
  46.     SHOW( for ( s = w; *s; s++ ) 
  47.           printf( isprint ( *s ) ? "%c" : " %dd ", *s); )
  48.     SHOW( printf ( "'" ); } )
  49.     in_counter = 1;
  50.     out_counter = 0;
  51.  
  52.     for(;;) {
  53.         for ( ; in_counter<bytes_read; in_counter++ ) {
  54.             int k;
  55.             code_type wk;
  56.  
  57.             k = in_buffer[in_counter];
  58.             SHOW( printf("\nIn: "); )
  59.             SHOW( printf ( isprint(k) ? "'%c'" : "%3dd", k ); )
  60.             if ( k == '\0' || /* NULLs are special */
  61.                ( wk = wk_is_in_table(w, k, string_table)) == 0) {
  62.                 write_out_code( w_code, out_buffer,
  63.                                 &out_counter, outfile );
  64.                 if ( k != '\0' && strlen ( w ) != 0 )
  65.                      put_wk_in_table( w_code, k,
  66.                                   string_table, &table_max );
  67.                 create_string( w, k );
  68.                 w_code = k;
  69.                 SHOW( { unsigned char *s; printf ( " w: '" ); )
  70.                 SHOW( for (s = w; *s; s++) printf(isprint(*s) ? 
  71.                         "%c" : " %dd ", *s ); )
  72.                 SHOW( printf ( "'" ); } )
  73.             }
  74.             /* wk is a known code, so note what we've found */
  75.             else {
  76.                 append_char( w, k );
  77.                 w_code = wk;
  78.                 SHOW( { unsigned char *s; printf (" w: '"); )
  79.                 SHOW( for ( s = w; *s; s++ ) 
  80.                       printf( isprint(*s) ? "%c" : " %dd ", *s);)
  81.                 SHOW( printf( "'" ); } )
  82.             }
  83.         }
  84.  
  85.         /* get another block */
  86.         if ( feof ( infile ))
  87.              break;
  88.         bytes_read = my_read ( infile, in_buffer,
  89.                      sizeof(unsigned char), IB_LENGTH_C );
  90.         in_counter = 0;
  91.     }
  92.  
  93.     /* code last string and quit */
  94.     write_out_code( w_code, out_buffer,
  95.                     &out_counter, outfile );
  96.     my_write ( outfile, out_buffer, sizeof ( code_type ), 
  97.                out_counter );
  98.     SHOW( print_string_table ( string_table, "DONE", 
  99.             BASE_TABLE + 1, table_max); )
  100. #if defined(STATS)
  101.     printf ("Table had %d entries at conclusion.\n", table_max);
  102.     printf ("Input file was %ld bytes.\n", ftell ( infile ));
  103.     printf ("Output file is %ld bytes.\n", ftell ( outfile ));
  104. #endif
  105. } /* ends compression_routine */
  106.  
  107. /*--------------------------------------------------------
  108.  * Output a string's code to out_buffer. If the out_buffer
  109.  * is full, it writes the buffer to the output file.
  110.  *------------------------------------------------------*/
  111. void write_out_code( code_type n,
  112.                      code_type *out_buffer,
  113.                      unsigned *out_counter,
  114.                      FILE *outfile )
  115. {
  116.     if( *out_counter >= OB_LENGTH_C ) {
  117.         my_write ( outfile, out_buffer,
  118.                  sizeof ( code_type ), *out_counter );
  119.         *out_counter = 0;
  120.     }
  121.  
  122.     SHOW( if (n <= BASE_TABLE && isprint(n)))
  123.     SHOW(    printf(" Out: '%c'", n); 
  124.              else printf(" Out: %3d", n);)
  125.     out_buffer[*out_counter] = n;
  126.     *out_counter += 1;
  127. } /* ends write_out_code */
  128.  
  129. /*--------------------------------------------------------
  130.  * search the string table to see if the string w
  131.  * with the character k appended to it is present.
  132.  *
  133.  * find k
  134.  * build string w2 = w + k
  135.  * if w == w2 then return result = 1
  136.  * if not, find k again
  137.  * if you cannot find k where w2 == w
  138.  *    then return result = 0
  139.  *------------------------------------------------------*/
  140. code_type wk_is_in_table( unsigned char *w, int k,
  141.                           table_item *string_table )
  142. {
  143.     unsigned wlen;
  144.     code_type i;
  145.  
  146.     wlen = strlen ( w );
  147.     /* as a special case, if w[] is empty, we never match */
  148.     if ( !wlen )
  149.          return 0;
  150.  
  151.     /* walk the linked list of possible matches */
  152.     for ( i = string_table[k].chain; i != k;
  153.           i = string_table[i].chain ) {
  154.         code_type walk;
  155.         unsigned char *s;
  156.         unsigned count;
  157.  
  158.         walk = string_table[i].num;
  159.         s = w + wlen - 1;  /* end of string */
  160.         for ( count = wlen; count > 0; count -- ) {
  161.             if ( *s != (unsigned char) 
  162.                     string_table[walk].character )
  163.                 break;
  164.             walk = string_table[walk].num;
  165.             s--;
  166.         }
  167.         if ( count == 0 && walk == 0 )
  168.              return (code_type) i;
  169.     }
  170.     return 0; /* if we get here, we didn't match */
  171. }
  172.  
  173. /*--------------------------------------------------------
  174.  * insert the string w and character
  175.  * k into the string table.
  176.  *-------------------------------------------------------*/
  177. void put_wk_in_table ( code_type w_code,
  178.                        int k,
  179.                        table_item *string_table,
  180.                        unsigned *tmax )
  181. {
  182.     /* watch for table overflow */
  183.     if ( *tmax == TABLE_SIZE - 1 )
  184.          return;
  185.  
  186.     /* enter into next available slot */
  187.     *tmax += 1;
  188.     string_table[*tmax].num       = w_code;
  189.     string_table[*tmax].character = k;
  190.  
  191.     /* put self at head of linked list */
  192.     string_table[*tmax].chain     = string_table[k].chain;
  193.     string_table[k].chain         = *tmax;
  194.  
  195.     SHOW( print_string_table(string_table, 
  196.             "ADD", *tmax, *tmax); )
  197. } /* ends put_wk_in_table */
  198.  
  199. /*--------------------------------------------------------
  200.  * take the number from the string table and use it
  201.  * to build a string w.
  202.  *------------------------------------------------------*/
  203. void build_string( unsigned char *w, code_type number,
  204.                    table_item *string_table )
  205. {
  206.     int count;
  207.     code_type walk;
  208.  
  209.     /* first, how long will the string be? */
  210.     for ( count=0, walk = number;
  211.            string_table[walk].character;
  212.            walk = string_table[walk].num )
  213.          count++;
  214.  
  215.     /* now, build the string */
  216.     w[count--] = 0; /* terminator */
  217.     walk = number;
  218.     for ( ; count >= 0; count-- ) {
  219.         w[count] = (unsigned char) string_table[walk].character;
  220.         walk = string_table[walk].num;
  221.     }
  222. }
  223.  
  224. /*--------------------------------------------------------
  225.  * take a character k and use it to create a
  226.  * 1 character long string w.
  227.  *------------------------------------------------------*/
  228. void create_string ( unsigned char *w, int k )
  229. {
  230.     w[0] = (unsigned char) k;
  231.     w[1] = '\0';
  232. }
  233.  
  234. /*--------------------------------------------------------
  235.  * append the character k onto the
  236.  * end of the string w.
  237.  *------------------------------------------------------*/
  238. void append_char ( unsigned char *w, int k )
  239. {
  240.     unsigned i;
  241.  
  242.     i = strlen ( w );
  243.     w[i] = (unsigned char) k;
  244.     w[i+1] = '\0';
  245. } /* ends append_char */
  246.  
  247. /*--------------------------------------------------------
  248.  * initialize() sets the first 256 items in string_table
  249.  * to represent the corresponding ASCII codes. The remainder
  250.  * of the table is set to zero. The number of elements in
  251.  * the base table is returned as the function's value.
  252.  *------------------------------------------------------*/
  253. unsigned initialize ( table_item *string_table )
  254. {
  255.     int i;
  256.     for ( i = 0; i <= BASE_TABLE; i++ ){
  257.         string_table[i].num = 0;
  258.         string_table[i].chain = i;
  259.         string_table[i].character = i;
  260.     }
  261.  
  262.     for( i = BASE_TABLE + 1; i < TABLE_SIZE; i++ ){
  263.         string_table[i].num = 0;
  264.         string_table[i].character = '\0';
  265.     }
  266.  
  267.     return BASE_TABLE;
  268. } /* ends initialize */